package algocasts;

import java.util.Stack;

public class P146_LargestRectangleInHistogram {
    // Time: O(n^2)  Space: O(1)    LeetCode 超时
    public int largestRectangleArea_Expand(int[] heights) {
        if (heights == null || heights.length == 0) return 0;
        int max = 0, n = heights.length;
        for (int i = 0; i < n; i++) {
            int l = i, r = i;
            while (l >= 0 && heights[l] >= heights[i]) l--;
            while (r < n && heights[r] >= heights[i]) r++;
            max = Math.max(max, heights[i] * (r - l - 1));
        }
        return max;
    }
    // Time: O(n)  Space: O(n)
    public int largestRectangleArea_Stack(int[] heights) {
        if (heights == null || heights.length == 0) return 0;
        int max = 0, n = heights.length;
        Stack<Integer> stack = new Stack<>();
        for (int r = 0; r <= n; r++) {
            int h = r == n ? 0 : heights[r];
            while (!stack.isEmpty() && h < heights[stack.peek()]) {
                int idx = stack.pop();
                int l = stack.isEmpty() ? -1 : stack.peek();
                max = Math.max(max, heights[idx] * (r - l - 1));
            }
            stack.push(r);
        }
        return max;
    }


}
